The aim of this article is to find an effective method for solving Variable-order fractional integro-differential equations. This method transforms the problem into a system of algebraic equations. For this purpose, we first express Vieta-Lucas orthogonal polynomials, then, we express the operational matrices of these polynomials. At this stage, all components of the equation will be expressed in terms of the new shifted Vieta-Lucas operational matrices. After that, by placing these operational matrices in the main equation and using the spectral collocation method, the Variable-order fractional integro-differential equation will become an algebraic system. By solving this algebraic system, we will find an approximate solution to the original equation. In the following, an analysis of the error is also presented by preparing some theorems. In the end, in order to express the efficiency and capability of the method, some numerical examples are given. Additionally, for the numerical examples, the condition number, numerical convergence order, and the computed CPU time are evaluated. Based on the obtained results, it was concluded that the proposed method is relatively stable, highly accurate and efficient, and has an appropriate convergence rate.